class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        return merge(nums, 0, n - 1);
    }
    public int merge(int[] nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int ret = 0;
        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = left;
        while (cur2 <= right) {
            while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
            if (cur1 > mid) break;
            ret += mid - cur1 + 1;
            cur2++;
        }
        cur1 = left;
        cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] < nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= right) {
            tmp[i++] = nums[cur2++];
        }
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j];
        }
        return ret;
    }
}